package com.le.high.class1;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个数组，求如果排序之后，相邻两数的最大差值。要求时间复杂度O(N)，且要求不能用非基于比较的排序。
 */
public class Problem01_MaxGap {

    public static int getMaxGap(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
        }
        // arr里只有一种元素
        if (min == max) {
            return 0;
        }
        int[] mins = new int[len + 1];
        int[] maxs = new int[len + 1];
        boolean[] isNum = new boolean[len + 1];
        int index = -1;
        for (int i = 0; i < len; i++) {
            index = getIndex(len, min, max, arr[i]);
            mins[index] = isNum[index] ? Math.min(mins[index], arr[i]) : arr[i];
            maxs[index] = isNum[index] ? Math.max(maxs[index], arr[i]) : arr[i];
            isNum[index] = true;
        }
        int res = 0;
        int preLast = maxs[0];
        for (int i = 1; i <= len; i++) {
            if (isNum[i]) {
                res = Math.max(res, mins[i] - preLast);
                preLast = maxs[i];
            }
        }
        return res;
    }

    public static int getIndex(int len, int min, int max, int val) {
        return (val - min) * len / (max - min);
    }


    // for test
    public static int compare(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        Arrays.sort(arr);
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < arr.length; i++) {
            res = Math.max(res, arr[i] - arr[i - 1]);
        }
        return res;
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    @Test
    public void test() {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if (getMaxGap(arr1) != compare(arr2)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }
}
